//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 
//
// 
// 
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[["Q"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 
// 
// 
// Related Topics 数组 回溯 👍 1333 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution51 {
    List<List<String>> result = new ArrayList<>();
    int[] cols = null;
    public List<List<String>> solveNQueens(int n) {
        cols = new int[n];
        backTracking(n, 0);
        return result;
    }

    public void backTracking(int n, int row){
        if(row == n){
            List<String>  list = changToString(cols);
            result.add(new ArrayList<>(list));
            return;
        }
        for(int col = 0; col < n; col++){
            if(check(row, col)){
                cols[row] = col;
                backTracking(n, row+1);
            }
        }
    }

    private List<String> changToString(int[] cols) {
        List<String> list = new ArrayList<>();
        for(int i = 0; i < cols.length; i++){
            StringBuffer sb = new StringBuffer();
            for(int j = 0; j < cols.length; j++){
                if(cols[i] == j){
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            list.add(sb.toString());
        }
        return list;
    }

    private boolean check(int row, int col) {
        for(int i = 0; i < row; i++){
            int colTmp = cols[i];
            if(col == colTmp) return false;
//            if((col-colTmp == row-i) || (col-colTmp == -(row-i))){
            if(row - i == Math.abs(col - colTmp)){ //简化的写法
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        List<List<String>> lists = new Solution51().solveNQueens(4);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
